package com.mgq.algorithm.dp;

/**
 * 给定一个数n,表示二叉树的node数,返回能形成多少种二叉树
 */
public class SumTree {


    /**
     *左树从0个节点,右树有多少种可能.
     *左树1个节点,右树有多少种可能.
     *左树2个节点,右树有多少种可能.
     *一直到左树有n-1个节点,右树有多少种可能
     * @param n
     * @return
     */
    public static int process(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        //左树从0开始,一直累加到n-1.穷举所有可能,得到的总和就是总的数
        int res=0;
        for (int leftNumber = 0; leftNumber <= n-1; leftNumber++) {
            int left = process(leftNumber);
            int right = process(n - leftNumber - 1);
            res += left * right;
        }
        return res;
    }

    public static int dp(int n) {
        int[] dp = new int[n+1];
        //0个节点是空树,返回一种方法
        dp[0] = 1;
        //要计算n个节点的返回值.返回dp[n]
        for (int i = 1; i < n + 1; i++) { //节点数是i的时候
            for (int j = 0; j <= i - 1; j++) { //左节点数的个数
                dp[i] += dp[j] * dp[i - j-1]; //总的值是 左侧节点*右侧
            }
        }
       return dp[n];
    }


    public static void main(String[] args) {
        System.out.println(process(5));
        System.out.println(dp(5));
    }
}
